package number_46;


import test.Solution1;

import java.util.*;

public class Solution {
    private List<List<Integer>> ret = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        LinkedList<Integer> list = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        backTrace(nums, list, visited);
        return ret;
    }

    private void backTrace(int[] nums, LinkedList<Integer> list, Set<Integer> visited) {
        if (list.size() == nums.length) {
            ret.add(new ArrayList<>(list));
            return;
        }
        for (int v : nums) {
            if (visited.contains(v)) {
                continue;
            }
            list.add(v);
            visited.add(v);
            backTrace(nums, list, visited);
            list.removeLast();
            visited.remove(v);
        }
    }

    public static void main(String[] args) {
        new Solution().permute(new int[] {1,2,3});
    }
}
